The structure of satisfiability problems is used to improve search algorithms for quantum computers and reduce their required coherence times. The asymptotic average behavior of the these algorithms is determined exactly, and used to identify the best algorithm from among a class of methods that use only a single coherent evaluation of problem properties. The resulting algorithm improves on previous quantum algorithms for most random k-SAT problems, but remains exponential for hard problem instances. Compared to good classical methods, the algorithm performs better, on average, for weakly and highly constrained problems but worse for hard cases, indicating the need to include additional problem structure in quantum algorithms.
展开▼
